package com.wrial.simple;
/*
 * @Author  Wrial
 * @Date Created in 16:37 2020/3/29
 * @Description 层次打印二叉树
 */

import java.util.*;

public class LeetCode_102_FaceTest32_II {

    LinkedList<List<Integer>> ans = new LinkedList<>();
    Deque<TreeNode> queueNodes = new LinkedList();

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return ans;
        queueNodes.add(root);
        addQueue();
        return ans;
    }

    private void addQueue() {
        // 标记这一层的最后一个节点
        TreeNode levelNode = queueNodes.peekLast();
        List<Integer> submit = new ArrayList<>();
        while (!queueNodes.isEmpty()) {

            TreeNode pollNode = queueNodes.poll();
                submit.add(pollNode.val);
            if (pollNode.left != null) queueNodes.offer(pollNode.left);
            if (pollNode.right != null) queueNodes.offer(pollNode.right);

            // 也可以在开始的时候记录一个count，每次--，小于0就表示这一层的结束
            if (pollNode == levelNode){
                // 把最后一个进去的给levelNode
                levelNode = queueNodes.peekLast();
                ans.add(submit);
                submit = new ArrayList<>();
            }


        }

    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}
